package leetcode.top100;

import java.util.Stack;

/**
 * 给定一个经过编码的字符串，返回它解码后的字符串。
 * <p>
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。
 * <p>
 * 注意 k 保证为正整数。
 * <p>
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 * <p>
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，
 * <p>
 * 例如不会出现像 3a 或 2[4] 的输入。
 * <p>
 * 示例:
 * <p>
 * s = "3[a]2[bc]", 返回 "aaabcbc".
 * s = "3[a2[c]]", 返回 "accaccacc".
 * s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
 * <p>
 * TODO 字符串编码见{@link Code471_EncodeString_字符串编码}
 *
 * @date 2020/5/5 23:50
 */
public class Code394_DecodeString_字符串解码 {

    public String decodeString(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        StringBuilder res = new StringBuilder();
        int count = 0;
        //存储字符串
        Stack<String> strStack = new Stack<>();
        //存储数字
        Stack<Integer> countStack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '[') {
                //入栈count和res
                strStack.push(res.toString());
                countStack.push(count);
                //重新计算
                count = 0;
                res = new StringBuilder();
            } else if (c == ']') {
                //如multi1*[ xxx multi2*[res] ]
                //计算最近的multi2*[res]，然后把和 [ 之前的xxx结合到一起
                int multi = countStack.pop();
                StringBuilder sb = new StringBuilder();
                while (multi-- != 0) {
                    sb.append(res);
                }
                res = new StringBuilder(strStack.pop() + sb.toString());
            } else if (c >= '0' && c <= '9') {
                //count可能大于10
                count = count * 10 + c - '0';
            } else {
                res.append(c);
            }
        }
        return res.toString();
    }

    public static void main(String[] args) {
        System.out.println(new Code394_DecodeString_字符串解码().decodeString("3[a]2[bc]"));
    }
}
